package lib;

import java.util.ArrayList;

public class ConvexHull {
	public ArrayList<Integer> resX = new ArrayList<Integer>();
	public ArrayList<Integer> resY = new ArrayList<Integer>();
	
	/** Method was tested and works well */
	public void calcConvexHull(int[] xs, int[] ys) {
		if(xs.length == 0) {
			return;
		}
		int sx = xs[0], sy = ys[0], ind = 0;
		// get the leftmost upper point - the first from hull
		for (int i = 1; i < ys.length; i++) {
	    if(sx > xs[i] || (sx == xs[i] && sy > ys[i])) {
	    	sx = xs[i];
	    	sy = ys[i];
	    	ind = i;
	    }
    }
		
		boolean[] inTheHull = new boolean[xs.length];
		resX.add(sx);
		resY.add(sy);
		inTheHull[ind] = true;
		
		int nx = 0, ny = 0;
		boolean nextFound = true;
		while(nextFound) {
			nextFound = false;
			/** quadrant 1 */
			for (int i = 0; i < xs.length; i++) {
	      if(ind == i) {
	      	continue;
	      }
	      
	      if(ys[i] > sy || xs[i] <= sx) {
	      	continue;
	      }
	      
	      if(!nextFound) {
	      	nextFound = true;
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      	continue;
	      }
	      
	      // need max of (sy - ys[i]) / (xs[i] - sx)
	      // meaning (sy - ys[i]) * (nx - sx) >= (sy - ny) * (xs[i] - sx)
	      int dif = (sy - ys[i]) * (nx - sx) - (sy - ny) * (xs[i] - sx);
	      if(dif > 0 || (dif == 0 &&
	      		(xs[i] - sx) * (xs[i] - sx) + (ys[i] - sy) * (ys[i] - sy) < 
	      		(nx - sx) * (nx - sx) + (ny - sy) * (ny - sy))) {
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      }
      }
			
			if(nextFound) {
				if(inTheHull[ind]) {
					break;
				}
				sx = nx;
				sy = ny;
				resX.add(sx);
				resY.add(sy);
				inTheHull[ind] = true;
			}
		}
		
		
		nextFound = true;
		while(nextFound) {
			nextFound = false;
			/** quadrant 2 */
			for (int i = 0; i < xs.length; i++) {
	      if(i == ind) {
	      	continue;
	      }
	      
	      if(ys[i] <= sy || xs[i] < sx) {
	      	continue;
	      }
	      
	      if(!nextFound) {
	      	nextFound = true;
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      	continue;
	      }
	      
	      // need min of (ys[i] - sy) / (xs[i] - sx)
	      // meaning (ys[i] - sy) * (nx - sx) <= (ny - sy) * (xs[i] - sx)
	      int dif = (ys[i] - sy) * (nx - sx) - (ny - sy) * (xs[i] - sx);
	      if(dif < 0 || (dif == 0 &&
	      		(xs[i] - sx) * (xs[i] - sx) + (ys[i] - sy) * (ys[i] - sy) < 
	      		(nx - sx) * (nx - sx) + (ny - sy) * (ny - sy))) {
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      }
      }
			
			if(nextFound) {
				if(inTheHull[ind]) {
					break;
				}
				sx = nx;
				sy = ny;
				resX.add(sx);
				resY.add(sy);
				inTheHull[ind] = true;
			}
		}

		
		nextFound = true;
		while(nextFound) {
			nextFound = false;
			/** quadrant 3 */
			for (int i = 0; i < xs.length; i++) {
	      if(i == ind) {
	      	continue;
	      }
	      
	      if(ys[i] < sy || xs[i] >= sx) {
	      	continue;
	      }
	      
	      if(!nextFound) {
	      	nextFound = true;
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      	continue;
	      }
	      
	      // need max of (ys[i] - sy) / (sx - xs[i])
	      // meaning (ys[i] - sy) * (sx - nx) >= (ny - sy) * (sx - xs[i])
	      int dif = (ys[i] - sy) * (sx - nx) - (ny - sy) * (sx - xs[i]);
	      if(dif > 0 || (dif == 0 &&
	      		(xs[i] - sx) * (xs[i] - sx) + (ys[i] - sy) * (ys[i] - sy) < 
	      		(nx - sx) * (nx - sx) + (ny - sy) * (ny - sy))) {
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      }
      }
			
			if(nextFound) {
				if(inTheHull[ind]) {
					break;
				}
				sx = nx;
				sy = ny;
				resX.add(sx);
				resY.add(sy);
				inTheHull[ind] = true;
			}
		}
		
		
		nextFound = true;
		while(nextFound) {
			nextFound = false;
			/** quadrant 4 */
			for (int i = 0; i < xs.length; i++) {
	      if(i == ind) {
	      	continue;
	      }
	      
	      if(ys[i] >= sy || xs[i] > sx) {
	      	continue;
	      }
	      
	      if(!nextFound) {
	      	nextFound = true;
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      	continue;
	      }
	      
	      // need min of (sy - ys[i]) / (sx - xs[i])
	      // meaning (sy - ys[i]) * (sx - nx) <= (sy - ny) * (sx - xs[i])
	      int dif = (sy - ys[i]) * (sx - nx) - (sy - ny) * (sx - xs[i]);
	      if(dif < 0 || (dif == 0 &&
	      		(xs[i] - sx) * (xs[i] - sx) + (ys[i] - sy) * (ys[i] - sy) < 
	      		(nx - sx) * (nx - sx) + (ny - sy) * (ny - sy))) {
	      	nx = xs[i];
	      	ny = ys[i];
	      	ind = i;
	      }
      }
			
			if(nextFound) {
				if(inTheHull[ind]) {
					break;
				}
				sx = nx;
				sy = ny;
				resX.add(sx);
				resY.add(sy);
				inTheHull[ind] = true;
			}
		}
	}
}
